#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""

import sys
sys.setrecursionlimit(2000)


class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None


class Solution:
    MAX_INT = 2 ** 32

    def minDepth(self, root):
        # NOTE: 根节点到叶子节点的距离!!!
        # NOTE: 注意如果根节点含有右子树, 但是没有左子树.(此时根节点不算叶子节点), 所以此时最低高度不是1 (注意叶子节点的定义)
        # NOTE: 没有左子树和右子树: 才算叶子节点!!!

        if not root:
            return 0

        # return self.rec_min_depth(root, self.MAX_INT, 0)
        # return self.bfs_min_depth(root)
        return self.bfs_min_depth_one_queue(root)

    # =================== bfs one queue  =====================
    def bfs_min_depth_one_queue(self, root):
        queue = [root]
        cur_depth = 1

        while queue:
            size = len(queue)

            while size > 0:
                node = queue.pop(0)
                if node.left is None and node.right is None:
                    return cur_depth

                if node.left:
                    queue.append(node.left)

                if node.right:
                    queue.append(node.right)

                size -= 1

            cur_depth += 1

    # =================== bfs two queue =====================
    def bfs_min_depth(self, root):
        two_queue = [[], [root]]        # 两个queue 来回倒腾!
        cur_depth = 1

        cur_idx = 0
        cur_idx, another_idx = 0, 1

        while True:

            # idx: loop method 2
            # cur_idx = (cur_idx + 1) % 2
            # another_idx = (cur_idx + 1) % 2

            # idx: loop method 2
            # cur_idx = (cur_depth ) % 2
            # another_idx = (cur_depth + 1) % 2

            # idx: loop method 3
            cur_idx, another_idx = another_idx, cur_idx
            two_queue[another_idx].clear()

            assert two_queue[cur_idx], cur_idx


            for node in two_queue[cur_idx]:
                # 遇到叶子节点: 返回
                if node.left is None and node.right is None:
                    return cur_depth

                if node.left:
                    two_queue[another_idx].append(node.left)

                if node.right:
                    two_queue[another_idx].append(node.right)

            cur_depth += 1

    # =================== rec =====================
    def rec_min_depth(self, node, global_min, sub_depth):
        # 传入当前最小深度是为了及时剪枝
        if (not node.left) and (not node.right):
            return sub_depth + 1

        # NOTE: 及时剪枝
        if sub_depth >= global_min:
            return global_min

        # 如果没有left节点并不是代表到此为止了: 如果没有left节点, 因为当前节点不是叶子节点, 需要继续遍历右子树
        if node.left:
            left_min = self.rec_min_depth(node.left, global_min, sub_depth+1)
            global_min = min(left_min, global_min)

        if node.right:
            right_min = self.rec_min_depth(node.right, global_min, sub_depth+1)
            global_min = min(right_min, global_min)

        return global_min


def build_tree(n):
    root = TreeNode(0)

    tail = root
    for i in range(n):
        node = TreeNode(i)
        tail.right = node
        tail = node

    return root.right


def main():
    print("start main")
    root = TreeNode(5)
    left = TreeNode(3)
    ll = TreeNode(4)
    root.left = left
    # left.left = ll
    root.right = ll

    # from q155_input import l

    s = Solution()
    l = build_tree(18000)
    ret = s.minDepth(l)
    print(ret)

if __name__ == "__main__":
    main()
